import Data.List.Split

main = do
    c <- getContents
    let ns = map words $ concat $ map (drop 1) $ chunksOf 2 $ tail $ lines c
        rs = map (\ys -> (product (map read ys)) `mod` 1234567) ns
    putStr $ unlines $ map show rs    